package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/10 17:13
 * https://leetcode.cn/problems/word-ladder/
 */
public class Title127II {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordLists = new HashSet<>();
        wordLists.addAll(wordList);
        if (!wordLists.contains(endWord)){
            return 0;
        }
        LinkedList<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Map<String, Integer> visited = new HashMap<>();
        visited.put(beginWord, 1);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                Integer len = visited.get(word);
                for (int j = 0; j < word.length(); j++) {
                    char[] chars = word.toCharArray();
                    for (char k = 'a'; k <= 'z'; k++) {
                        if (chars[j] != k) {
                            chars[j] = k;
                            String newWord = String.valueOf(chars);
                            if (newWord.equals(endWord)) {
                                return len + 1;
                            }
                            if (wordLists.contains(newWord) && !visited.containsKey(newWord)) {
                                queue.offer(newWord);
                                visited.put(newWord, len + 1);
                            }
                        }
                    }
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {

    }
}
